""""
题目：基于模拟退火算法的TSP
姓名：不去幼儿园
最终修改时间：2023.12.30
"""
import math  # 导入模块 math
import random  # 导入模块 random
import pandas as pd  # 导入模块 pandas 并简写成 pd
import numpy as np  # 导入模块 numpy 并简写成 np YouCans
import matplotlib.pyplot as plt  # 导入模块 matplotlib.pyplot 并简写成 plt

plt.rcParams['font.sans-serif'] = ['Microsoft YaHei']  # 使用微软雅黑字体
plt.rcParams['axes.unicode_minus'] = False  # 处理负号显示异常

np.set_printoptions(precision=4)
pd.set_option('display.max_rows', 20)
pd.set_option('expand_frame_repr', False)
pd.options.display.float_format = '{:,.2f}'.format


# 子程序：初始化模拟退火算法的控制参数
def initParameter():
	tInitial = 100.0  # 设定初始退火温度(initial temperature)
	tFinal = 1  # 设定终止退火温度(stop temperature)
	nMarkov = 1000  # Markov链长度，也即内循环运行次数
	alfa = 0.98  # 设定降温参数，T(k)=alfa*T(k-1)
	return tInitial, tFinal, alfa, nMarkov


# 子程序：读取TSPLib数据
def read_TSPLib(fileName):
	res = []
	with open(fileName, 'r') as fid:
		for item in fid:
			if len(item.strip()) != 0:
				res.append(item.split())
	loadData = np.array(res).astype('int')  # 数据格式：i Xi Yi
	City = loadData[:, 1::]
	return City


# 子程序：计算各城市间的距离，得到距离矩阵
def getDistMat(nCities, City):
	distMat = np.zeros((nCities, nCities))  # 初始化距离矩阵
	for i in range(nCities):
		for j in range(i, nCities):
			# np.linalg.norm 求向量的范数（默认求 二范数），得到 i、j 间的距离
			distMat[i][j] = distMat[j][i] = round(np.linalg.norm(City[i] - City[j]))
	return distMat  # 城市间距离取整（四舍五入）


# 子程序：计算 TSP 路径长度
def calTourMileage(tourGiven, nCities, distMat):
	mileageTour = distMat[tourGiven[nCities - 1], tourGiven[0]]  # dist((n-1),0)
	for i in range(nCities - 1):  # dist(0,1),...dist((n-2)(n-1))
		mileageTour += distMat[tourGiven[i], tourGiven[i + 1]]
	return round(mileageTour)  # 路径总长度取整（四舍五入）


# 绘制 TSP 路径图
def plot_tour(tour, value, City):
	num = len(tour)
	x0, y0 = City[tour[num - 1]]
	x1, y1 = City[tour[0]]
	plt.scatter(int(x0), int(y0), s=15, c='r')  # 绘制城市坐标点 C(n-1)
	plt.plot([x1, x0], [y1, y0], c='b')  # 绘制旅行路径 C(n-1)~C(0)
	for i in range(num - 1):
		x0, y0 = City[tour[i]]
		x1, y1 = City[tour[i + 1]]
		plt.scatter(int(x0), int(y0), s=15, c='r')  # 绘制城市坐标点 C(i)
		plt.plot([x1, x0], [y1, y0], c='b')  # 绘制旅行路径 C(i)~C(i+1)
	plt.xlabel("Total mileage of the tour:{:.1f}".format(value))
	plt.title("Optimization tour of TSP{:d}".format(num))  # 设置图形标题
	plt.show()


# 交换操作算子
def mutateSwap(tourGiven, nCities):
	# 在 [0,n) 产生 2个不相等的随机整数 i,j
	i = np.random.randint(nCities)  # 产生第一个 [0,n) 区间内的随机整数
	while True:
		j = np.random.randint(nCities)  # 产生一个 [0,n) 区间内的随机整数
		if i != j: break  # 保证 i, j 不相等
	tourSwap = tourGiven.copy()  # 将给定路径复制给新路径 tourSwap
	tourSwap[i], tourSwap[j] = tourGiven[j], tourGiven[i]  # 交换 城市 i 和 j 的位置————简洁的实现方法
	return tourSwap


def SA_TSP(coordinates):
	# 模拟退火算法参数设置
	tInitial, tFinal, alfa, nMarkov = initParameter()  # 调用子程序，获得设置参数
	nCities = coordinates.shape[0]  # 根据输入的城市坐标 获得城市数量 nCities
	distMat = getDistMat(nCities, coordinates)  # 调用子程序，计算城市间距离矩阵
	nMarkov = nCities  # Markov链 的初值设置
	tNow = tInitial  # 初始化 当前温度(current temperature)
	# 初始化准备
	tourNow = np.arange(nCities)  # 产生初始路径，返回一个初值为0、步长为1、长度为n 的排列
	valueNow = calTourMileage(tourNow, nCities, distMat)  # 计算当前路径的总长度 valueNow
	tourBest = tourNow.copy()  # 初始化最优路径，复制 tourNow
	valueBest = valueNow  # 初始化最优路径的总长度，复制 valueNow
	recordBest = []  # 初始化 最优路径记录表
	recordNow = []  # 初始化 最优路径记录表
	# 开始模拟退火优化过程
	iter = 0  # 外循环迭代次数计数器
	while tNow >= tFinal:  # 外循环，直到当前温度达到终止温度时结束
		# 在当前温度下，进行充分次数(nMarkov)的状态转移以达到热平衡
		for k in range(nMarkov):  # 内循环，循环次数为Markov链长度
			# 产生新解：
			tourNew = mutateSwap(tourNow, nCities)  # 通过 交换操作 产生新路径
			valueNew = calTourMileage(tourNew, nCities, distMat)  # 计算当前路径的总长度
			deltaE = valueNew - valueNow
			# 接受判别：按照 Metropolis 准则决定是否接受新解
			if deltaE < 0:  # 更优解：如果新解的目标函数好于当前解，则接受新解
				accept = True
				if valueNew < valueBest:  # 如果新解的目标函数好于最优解，则将新解保存为最优解
					tourBest[:] = tourNew[:]
					valueBest = valueNew
			else:  # 容忍解：如果新解的目标函数比当前解差，则以一定概率接受新解
				pAccept = math.exp(-deltaE / tNow)  # 计算容忍解的状态迁移概率
				if pAccept > random.random():
					accept = True
				else:
					accept = False
			# 保存新解
			if accept == True:  # 如果接受新解，则将新解保存为当前解
				tourNow[:] = tourNew[:]
				valueNow = valueNew
		# 平移当前路径，以解决变换操作避开 0,（n-1）所带来的问题，并未实质性改变当前路径。
		tourNow = np.roll(tourNow, 2)  # 循环移位函数，沿指定轴滚动数组元素
		# 完成当前温度的搜索，保存数据和输出
		recordBest.append(valueBest)  # 将本次温度下的最优路径长度追加到 最优路径记录表
		recordNow.append(valueNow)  # 将当前路径长度追加到 当前路径记录表
		print('迭代次数i:{}, 当前温度(i):{:.2f}, 当前路径长度:{:.1f}, 最优路径长度:{:.1f}'.format(iter + 1, tNow,
																								  valueNow, valueBest))
		# 缓慢降温至新的温度，
		iter = iter + 1
		tNow = tNow * alfa  # 指数降温曲线：T(k)=alfa*T(k-1)
	return tourBest


def Draw_City(City, X):
	X = list(X)
	X.append(X[0])  # 再最后再回到出发的城市
	coor_x = []
	coor_y = []
	for i in X:
		i = int(i)
		coor_x.append(City[i][0])  # 按照最优路径顺序将所有城市的x轴坐标写入coor_x中
		coor_y.append(City[i][1])

	plt.figure(1)
	for i in range(len(X) - 1):
		plt.quiver(coor_x[i], coor_y[i], coor_x[i + 1] - coor_x[i], coor_y[i + 1] - coor_y[i],
				   color='r', width=0.005, angles='xy', scale=1, scale_units='xy')
	plt.quiver(coor_x[-1], coor_y[-1], coor_x[0] - coor_x[-1], coor_y[0] - coor_y[-1],
			   color='r', width=0.005, angles='xy', scale=1, scale_units='xy')
	plt.title('基于模拟退火算法的TSP')
	plt.show()


if __name__ == '__main__':
	# 随机生成城市信息
	nCity = 50
	City = np.random.uniform(0, 2000, [nCity, 2])  # uniform()生成nCity个二维数组，数值范围是0到2000
	# 执行算法
	Best_X = SA_TSP(City)
	# 画路径图
	Draw_City(City, Best_X)